home *** CD-ROM | disk | FTP | other *** search
Text File | 1997-01-03 | 20.2 KB | 798 lines | [TEXT/R*ch] |
- // ---------------------------------------------------------
- // RouterRules.cp
- //
- // Memory requirements
- // -------------------
- // About 12K of static tables. A variable amount of heap
- // memory. The program will run faster and/or yield
- // compacter results given more memory (in most cases).
- // The maximum amount of dynamic memory is approximately
- // (chunkSize+1)^chunkCount times the size of a pointer +
- // the number of input values times 12 bytes (the size of
- // BitGrpEntry). 'chunkSize' is 1, 2, 4 or 8. 'chunkCount'
- // is the width (in bits) of the input values / chunkSize,
- // rounded up. 'chunkCount' is between 4 and 32, inclusive.
- //
- // How it works
- // ------------
- // - The values to be reduced are arranged in memory in
- // a number of linked lists. The program then loops
- // through these lists trying to find values (with matching
- // masks) that differ in exactly one bit ('buddy' values).
- // The value in a pair of such compatible
- // values that has a '1' in the only differing bit position
- // is thrown away and the mask of the the remaining value
- // is updated by clearing that bit. If, for a given value
- // no 'buddy' can be found, it is output and the program
- // continues until all the internal lists are empty.
- //
- // - The values are arranged in 'bit groups' to quickly
- // locate a given value's buddy. A
- // bit group is identified by a number whose individual
- // digits denote the number of bits set to 1 within a range
- // of consecutive bits in the input value. A range of
- // consecutive bits is called a 'chunk'. Chunk sizes can
- // be 1, 2, 4 or 8. For example, an input value of 16 bits
- // that looks like this (chunkSize 4):
- // 1101 1001 0001 0111, will have group value 3213 (base 5,
- // since every digit denotes the number of 1's (0..4) per
- // bit sequence (chunk). During initialization,
- // all the input values are categorized using that scheme
- // by storing them in lists (one list for every bit group).
- // Pointers to the first elements (BitGrpEntry's) of these
- // lists are kept in the gBitGrpLists array. A particular
- // bit group can now be accessed using the bit group
- // value as an index into that array. For any given value,
- // to locate a buddy, only those
- // bit group lists have to be searched that differ by 1 in
- // exactly one digit.
- //
- // - The class BitGrpMapper is responsible for the
- // initial categorization of the input values (through
- // one of three lookup tables, depending on chunkSize).
- // The class also calculates and stores some
- // other values pertaining to the current run's chunk size.
- // The bulk of the base 3, 5 or 9 arithmetic (namely, when
- // for a given value the buddy groups have to be located)
- // is done in RemoveLoop(). For the chunkSize == 1 case,
- // no lookup table is required because the bit group
- // number is a binary number. Some of the functions have
- // been optimized for the 1 bit case.
- //
- // I think the algorithm is quite nice. However, there is
- // some room for improvement in the implementation.
- // Moreover, the style of the code could be improved - it
- // is not particularly readable and it doesn't make enough
- // use of types to make the code more expresive (basically
- // another one of those C turned C++ programs - I'm
- // working on it).
- // ---------------------------------------------------------
-
-
- #define ALTER_INPUT_VALUES 1
-
-
- #include "ProvidedCode.h"
- #include "BitGrpMapper.h"
-
-
- // Data structs and types
-
- enum ErrCode { kNoErr = 0,
- kErr = 1
- };
-
- struct BitGrpEntry {
- BitGrpEntry *next;
- ulng value;
- ulng mask;
- };
-
- typedef BitGrpEntry *BitGrpEntryPtr;
-
-
- // Prototypes
-
- ErrCode Init( void );
-
- ErrCode Process( void );
-
- long CleanUp( void );
-
- void MakeComplement( void );
-
- void InitBitGrpLists( long startValue,
- long pastValue );
-
- void ClearMemory( long *p,
- long blockCount );
-
- void ProcessLists( void );
-
- long RemoveValues( void );
-
- void RemoveLoop( long curIdx,
- BitGrpEntryPtr beforeEntry,
- BitGrpEntryPtr curEntry );
-
- void RemoveLoop1Bit( ulng curIdx,
- BitGrpEntryPtr beforeEntry,
- BitGrpEntryPtr curEntry );
-
-
- long ScanAndKeep( BitGrpEntryPtr compareEntry,
- BitGrpEntryPtr beforeEntry,
- ulng mask,
- ulng matchBit );
-
- long ScanAndRemove( BitGrpEntryPtr compareEntry,
- BitGrpEntryPtr beforeEntry,
- ulng mask,
- ulng matchBit );
-
- inline long Match( BitGrpEntryPtr compareEntry,
- BitGrpEntryPtr thisEntry,
- ulng matchBit );
-
- void AddToOutput( BitGrpEntryPtr curEntry );
-
-
- // global data
-
- long *gAllowedValues;
- long gNumAllowedValues;
- long gNumBits;
- Rule *gCurRule;
- long gMaxRules;
- long gRulesLeft;
- long gBlockNumAllowedValues;
- long gStartMask;
- long gAllow;
-
- BitGrpMapper gBitGrpMapper; // the BitGrpMapper class
- BitGrpEntryPtr *gBitGrpLists; // Array of BitGrpEntry
- // list headers
- BitGrpEntryPtr gFirstFreeEntry;
- long gNumBitGrpBlocks;
- long gNumValuesInLists;
-
-
- // Implementation
-
-
- // For any run, depending on the number of input values
- // and the amount of available memory, various combinations
- // of chunkSize and gBlockNumAllowedValues are possible,
- // yielding different results and different execution times.
- // There wasn't enough time to sufficiently analyze the
- // program's algorithm. That's why this function contains
- // a lot of guessing. The while loop in Init() starts with
- // a small chunkSize (1 or 2) and tries to allocate the
- // required amount of memory. If that fails, the number
- // of input values processed at a time is split in half,
- // requiring less memory for the actual values. If that
- // still takes too much memory, the chunkSize is increased,
- // the number of values to be processed is reset and the
- // attempt to allocate memory is repeated.
- //
- ErrCode Init( void )
- {
- const long kBitLimit = 27;
- const long kMemLimit = 1L << kBitLimit;
- long valueMem;
- long splitCount = 0;
- long chunkSize = 1;
-
- gBitGrpLists = NULL;
- gBlockNumAllowedValues = gNumAllowedValues;
- if (gNumBits > kBitLimit) chunkSize = 2;
-
- while (gBlockNumAllowedValues > 0) {
-
- // Init gBitGrpMapper fur current chunk size
- gBitGrpMapper.Init( chunkSize, gNumBits );
-
- if (splitCount == 0 && chunkSize != 8 &&
- gBitGrpMapper.numGrpLists / gBlockNumAllowedValues
- > 60) {
- // Very scarce -> Force shift to next chunk size
- splitCount = 100;
-
- } else {
-
- if ( 4 * gBitGrpMapper.numGrpLists < kMemLimit) {
-
- // How many blocks of 8 BitGrpEntryPtr's?
- gNumBitGrpBlocks = gBitGrpMapper.numGrpLists/8 + 1;
-
- // How much memory for the values
- valueMem =
- gBlockNumAllowedValues * sizeof( BitGrpEntry );
-
- if (valueMem < kMemLimit) {
-
- // Allocate memory for the BitGrpEntry's
- gBitGrpLists = (BitGrpEntryPtr*)
- NewPtr(valueMem + 32 * gNumBitGrpBlocks);
-
- // Successful allocation?
- if (gBitGrpLists) {
- gFirstFreeEntry = (BitGrpEntryPtr)
- &gBitGrpLists[ 8 * gNumBitGrpBlocks ];
- return kNoErr;
- }
- }
- }
- }
-
- switch (chunkSize) {
- case 1:
- if (splitCount>=1 || gBlockNumAllowedValues < 4) {
- gBlockNumAllowedValues = gNumAllowedValues;
- splitCount = 0;
- chunkSize = 2;
- continue;
- }
- case 2:
- if (splitCount>=2 || gBlockNumAllowedValues < 4) {
- gBlockNumAllowedValues = gNumAllowedValues;
- splitCount = 0;
- chunkSize = 4;
- continue;
- }
- case 4:
- if (splitCount>=3 || gBlockNumAllowedValues < 4) {
- gBlockNumAllowedValues = gNumAllowedValues;
- splitCount = 0;
- chunkSize = 8;
- continue;
- }
- }
-
- gBlockNumAllowedValues /= 2;
- splitCount++;
- }
-
- return kErr;
- }
-
-
- // If the number of allowed values in the input exceeds
- // half the maximum number of allowed values (plus some
- // slack), the number of values that are not in the
- // gAllowedValues array are calculated and replace the
- // values in gAllowedValues. These values are then to be
- // denied.
- //
- void MakeComplement( void )
- {
- ulng *bitMap;
- ulng numLongs = (1L << gNumBits) / 32;
-
- bitMap = (ulng*) NewPtr( 4 * (numLongs + 8));
-
- if (bitMap) {
-
- // Clear bitMap
- ClearMemory( (long*)bitMap, (numLongs + 8) / 8 );
-
- // For every allowed value set its bit in bitMap
- ulng *pastVal=(ulng*)&gAllowedValues[gNumAllowedValues];
- ulng *curVal = (ulng*)gAllowedValues;
-
- do {
- bitMap[*curVal>>5] |= (1L << (*curVal & 0x0000001f));
- curVal++;
- } while (curVal != pastVal);
-
- // Determine the values to be denied by looking for
- // 0 bits in bitMap. Write them out to gAllowedValues
- ulng *curEntry = bitMap;
- ulng curIndex; // into bitMap
- ulng curBit;
- curVal = (ulng*)gAllowedValues;
-
- for (curIndex = 0; curIndex<numLongs; curIndex++) {
- if (*curEntry != 0xffffffff) {
- for (curBit = 0; curBit<32; curBit++) {
- if ((*curEntry & (1L << curBit)) == 0) {
- *curVal = (curIndex << 5) | curBit;
- curVal++;
- }
- }
- }
- curEntry++;
- }
-
- // Set the new number of values in gAllowedValues
- // and flip the gAllow variable from kAllow to kDeny
- gNumAllowedValues = curVal - (ulng*)gAllowedValues;
- gAllow = kDeny;
-
- DisposPtr( (char*) bitMap );
- }
- }
-
-
- // Initialization of the internal lists by reading
- // values from gAllowedValues and storing them as
- // BitGrpEntry items.
- //
- void InitBitGrpLists( long startValue,
- long pastValue )
- {
- long *curVal = &gAllowedValues[startValue];
- long *pastVal = &gAllowedValues[pastValue];
- BitGrpEntryPtr curEntry = gFirstFreeEntry;
- BitGrpEntryPtr *curHead;
-
- ClearMemory( (long*)gBitGrpLists, gNumBitGrpBlocks );
-
- // Two times the same while loop. Once for the special
- // case of chunkSize == 1 and then for the general
- // case of chunkSize == 2, 4 or 8. Only the chunkSize
- // == 2, 4 and 8 cases need gBitGrpMapper's LookUp method
- // since these cases deal with base 3, 5 and 9 integers,
- // respectively.
-
- if (gBitGrpMapper.chunkSize == 1) {
- while (curVal < pastVal) {
- gBitGrpLists[ *curVal ] = curEntry;
- curEntry->next = NULL;
- curEntry->value = *curVal;
- curEntry->mask = gStartMask;
- curEntry++;
- curVal++;
- }
- } else {
- while (curVal < pastVal) {
- curHead =
- &gBitGrpLists[ gBitGrpMapper.LookUp( *curVal ) ];
- curEntry->next = *curHead;
- curEntry->value = *curVal;
- curEntry->mask = gStartMask;
- *curHead = curEntry;
- curEntry++;
- curVal++;
- }
- }
-
- gNumValuesInLists = pastValue - startValue;
- }
-
-
- // Unfortunately I don't know the PPC processors well
- // enough to know whether the way this loop is unrolled
- // really helps much.
- //
- void ClearMemory( long *p,
- long blockCount )
- {
- while (blockCount--) {
- *p = NULL;
- p++;
- *p = NULL;
- p++;
- *p = NULL;
- p++;
- *p = NULL;
- p++;
- *p = NULL;
- p++;
- *p = NULL;
- p++;
- *p = NULL;
- p++;
- *p = NULL;
- p++;
- }
- }
-
-
- // Add a value for which no 'buddy' can be found to the
- // output array.
- //
- inline void AddToOutput( BitGrpEntryPtr curEntry )
- {
- if (gRulesLeft) {
- // Add to output rules
- gCurRule->value = curEntry->value;
- gCurRule->mask = curEntry->mask;
- gCurRule->allow = gAllow;
- gCurRule++;
- gRulesLeft--;
- }
- }
-
-
- // Entry point for the main processing loop. If there is
- // enough memory, all the available values are considered
- // at the same time. If memory is low, the input values
- // are processed in blocks of size gBlockNumAllowedValues
- // (likely to produce a higer number of output rules).
- //
- ErrCode Process( void)
- {
- long numValuesLeft = gNumAllowedValues;
- long startValue = 0;
- long pastValue = 0;
-
- while (numValuesLeft) {
-
- pastValue += gBlockNumAllowedValues;
- if (pastValue > gNumAllowedValues) {
- pastValue = gNumAllowedValues;
- }
- InitBitGrpLists( startValue, pastValue );
- ProcessLists();
- if (gRulesLeft <= 0) return kErr; // Output array full
- numValuesLeft -= pastValue - startValue;
- startValue = pastValue;
- }
-
- return kNoErr;
- }
-
-
- // Loop over gBitGrpLists while there are values
- // to combine.
- //
- void ProcessLists( void )
- {
- while (gNumValuesInLists) {
- gNumValuesInLists -= RemoveValues();
- }
- }
-
-
- // One loop over gBitGrpLists, combining pairs of values
- // that differ in exactly one bit. If for a given value
- // such a compatible value is found (referred to as 'buddy'
- // in many places in the code), they are combined. This is
- // done by 'throwing away' the value that has a '1' in
- // the bit position that differs and then clearing the
- // same bit in the remaining value's mask.
- //
- long RemoveValues( void )
- {
- long valuesRemoved = 0;
- long curIdx = 0;
- BitGrpEntryPtr beforeEntry;
- BitGrpEntryPtr curEntry;
- BitGrpEntryPtr *curList = gBitGrpLists;
- BitGrpEntryPtr *pastList =
- &gBitGrpLists[ gBitGrpMapper.numGrpLists ];
-
- if (gBitGrpMapper.chunkSize == 1) {
-
- while (curList < pastList) {
- if (*curList) {
- beforeEntry = (BitGrpEntryPtr)curList;
- curEntry = *curList;
- RemoveLoop1Bit( curIdx, beforeEntry, curEntry );
- valuesRemoved++;
- }
- curList++;
- curIdx++;
- }
-
- } else {
-
- while (curList < pastList) {
- if (*curList) {
- beforeEntry = (BitGrpEntryPtr)curList;
- curEntry = *curList;
- do {
- RemoveLoop( curIdx, beforeEntry, curEntry );
- valuesRemoved++;
- if (beforeEntry->next == curEntry) {
- beforeEntry = curEntry;
- }
- curEntry = curEntry->next;
- } while (curEntry);
- }
- curList++;
- curIdx++;
- }
- }
-
- return valuesRemoved;
- }
-
-
- // RemoveLoop deals with chunkSize == 2, 4 and 8. This
- // Function loops over curEntry's buddy lists (lists that
- // may contain values that, compared with the value in
- // curEntry, differ in exactly one bit).
- //
- void RemoveLoop( long curIdx,
- BitGrpEntryPtr beforeEntry,
- BitGrpEntryPtr curEntry )
- {
- short curChunk = gBitGrpMapper.chunkCount;
- ulng mask = gBitGrpMapper.firstMask;
- ulng matchBit = gBitGrpMapper.firstMatchBit;
- long magIdx = curIdx;
- long magStep;
- ulng scanVal;
- BitGrpEntryPtr *buddyList;
-
- while (curChunk) {
-
- scanVal = curEntry->value & ~mask;
- magStep = gBitGrpMapper.lbTable[curChunk];
- if (magIdx < gBitGrpMapper.ubTable[curChunk]) {
-
- buddyList = &gBitGrpLists[ curIdx + magStep ];
- if (*buddyList) {
- if (ScanAndRemove( curEntry,
- (BitGrpEntryPtr)buddyList, ~mask, matchBit )) {
-
- return; // Found a 'buddy'
- }
- }
- }
-
- if (magIdx >= magStep) {
- buddyList = &gBitGrpLists[ curIdx - magStep ];
- if (*buddyList) {
- if (ScanAndKeep( curEntry,
- (BitGrpEntryPtr)buddyList, ~mask, matchBit )) {
-
- // remove curEntry from list
- beforeEntry->next = curEntry->next;
- return; // Found a 'buddy'
- }
- }
-
- do {
- magIdx -= magStep;
- } while (magIdx >= magStep);
- }
-
- mask >>= gBitGrpMapper.chunkSize;
- matchBit >>= gBitGrpMapper.chunkSize;
- curChunk--;
- }
-
- // No match found -> add to output and remove from list
- AddToOutput( curEntry );
- beforeEntry->next = curEntry->next;
-
- }
-
-
- // The 1 bit only version of RemoveLoop()
- //
- void RemoveLoop1Bit ( ulng curIdx,
- BitGrpEntryPtr beforeEntry,
- BitGrpEntryPtr curEntry )
- {
- ulng matchBit = gBitGrpMapper.firstMatchBit;
- BitGrpEntryPtr *buddyHead;
-
- while (matchBit) {
-
- if (curIdx & matchBit) {
-
- if (buddyHead = &gBitGrpLists[ curIdx & ~matchBit ]) {
- if ((*buddyHead)->mask == curEntry->mask) {
- (*buddyHead)->mask &= ~matchBit;
- beforeEntry->next = NULL;
- return;
- }
- }
-
- } else {
-
- if (buddyHead = &gBitGrpLists[ curIdx | matchBit ]) {
- if ((*buddyHead)->mask == curEntry->mask) {
- curEntry->mask &= ~matchBit;
- *buddyHead = NULL;
- return;
- }
- }
- }
-
- matchBit >>= 1;
- }
-
- AddToOutput( curEntry );
-
- beforeEntry->next = NULL;
- }
-
-
- // For a given value, scans through a group list and
- // searches for a buddy for that value. If a buddy
- // is found, compareEntry will be removed by
- // RemoveValues().
- //
- long ScanAndKeep( BitGrpEntryPtr compareEntry,
- BitGrpEntryPtr beforeEntry,
- ulng mask,
- ulng matchBit )
- {
- BitGrpEntryPtr thisEntry = beforeEntry->next;
- ulng scanValue = compareEntry->value & mask;
-
- while (thisEntry) {
- if ((thisEntry->value & mask) == scanValue) {
- if (compareEntry->mask == thisEntry->mask) {
- if (Match( compareEntry, thisEntry, matchBit)) {
-
- thisEntry->mask &= ~(compareEntry->value ^
- thisEntry->value);
- return 1;
- }
- }
- }
- beforeEntry = thisEntry;
- thisEntry = thisEntry->next;
- }
-
- return 0;
- }
-
-
- // Same as ScanAndKeep() except that if a buddy is found,
- // it is removed after the compareEntry's mask has been
- // updated (see RemoveValues()).
- //
- long ScanAndRemove( BitGrpEntryPtr compareEntry,
- BitGrpEntryPtr beforeEntry,
- ulng mask,
- ulng matchBit )
- {
- BitGrpEntryPtr thisEntry = beforeEntry->next;
- ulng scanValue = compareEntry->value & mask;
-
- while (thisEntry) {
- if ((thisEntry->value & mask) == scanValue) {
- if (compareEntry->mask == thisEntry->mask) {
- if (Match( compareEntry, thisEntry, matchBit)) {
-
- compareEntry->mask &= ~(compareEntry->value ^
- thisEntry->value);
- beforeEntry->next = thisEntry->next;
- return 1;
- }
- }
- }
- beforeEntry = thisEntry;
- thisEntry = thisEntry->next;
- }
-
- return 0;
- }
-
-
- // The two values compareEntry->value and
- // thisEntry->value can be combined if they differ in
- // exactly one bit. In those cases, refVal, below, will
- // have exactly one bit set. The rest of the code
- // tests to see if that is so. I have the feeling that
- // this function's efficiency could be improved.
- //
- inline long Match( BitGrpEntryPtr compareEntry,
- BitGrpEntryPtr thisEntry,
- ulng matchBit )
- {
- ulng refVal = compareEntry->value ^ thisEntry->value;
- ulng matchCount = 0;
-
- switch (gBitGrpMapper.chunkSize) {
- case 2:
- if (! (refVal ^ matchBit)) return 1;
- matchBit >>= 1;
- if (! (refVal ^ matchBit)) return 1;
- return 0;
- case 4:
- if (! (refVal ^ matchBit)) return 1;
- matchBit >>= 1;
- if (! (refVal ^ matchBit)) return 1;
- matchBit >>= 1;
- if (! (refVal ^ matchBit)) return 1;
- matchBit >>= 1;
- if (! (refVal ^ matchBit)) return 1;
- return 0;
- case 8:
- if (! (refVal ^ matchBit)) return 1;
- matchBit >>= 1;
- if (! (refVal ^ matchBit)) return 1;
- matchBit >>= 1;
- if (! (refVal ^ matchBit)) return 1;
- matchBit >>= 1;
- if (! (refVal ^ matchBit)) return 1;
- matchBit >>= 1;
- if (! (refVal ^ matchBit)) return 1;
- matchBit >>= 1;
- if (! (refVal ^ matchBit)) return 1;
- matchBit >>= 1;
- if (! (refVal ^ matchBit)) return 1;
- matchBit >>= 1;
- if (! (refVal ^ matchBit)) return 1;
- return 0;
- }
- return 0;
- }
-
-
- // I first developped this solution using the Symantec
- // environment where I used the C++ new and delete
- // functions for memory management. After moving to
- // CodeWarrior, however, I had to use the Mac Toolbox
- // function NewPtr to allocate memory in Init() (and
- // DisposPtr to dispose of it here) because Codewarrior's
- // implementation of new didn't seem to reliably return
- // NULL in cases a memory request could not be
- // satisfied.
- //
- long CleanUp( void )
- {
- if (gBitGrpLists) DisposPtr( (char*)gBitGrpLists );
-
- if (gRulesLeft > 0) {
- gCurRule->value = 0;
- gCurRule->mask = 0;
- if (gAllow == kAllow) {
- gCurRule->allow = kDeny;
- } else {
- gCurRule->allow = kAllow;
- }
- gRulesLeft--;
-
- return gMaxRules - gRulesLeft;
- } else {
- return -1;
- }
-
- }
-
-
- // Main entry point
- //
- long RouterRules( long allowedValues[],
- long numAllowedValues,
- long numBits,
- Rule rulesArray[],
- long maxRules )
- {
- gAllowedValues = allowedValues;
- gNumAllowedValues = numAllowedValues;
- gNumBits = numBits;
- gCurRule = rulesArray;
- gMaxRules = maxRules;
- gRulesLeft = maxRules;
- gStartMask = 0xffffffff >> (32-gNumBits);
- gAllow = kAllow;
-
- if (maxRules <= 0) return -1;
-
- if (numAllowedValues <= 0) {
- gCurRule->mask = 0;
- gCurRule->value = 0;
- gCurRule->allow = kDeny;
- return 1;
- }
- if (numAllowedValues == (1L << numBits)) {
- gCurRule->mask = 0;
- gCurRule->value = 0;
- gCurRule->allow = kAllow;
- return 1;
- }
-
- #if ALTER_INPUT_VALUES == 1
- if (numBits > 5 && numBits < 32 && numAllowedValues >
- ( (1L<<(numBits-1)) + (1L<<(numBits-5)) )) {
- MakeComplement();
- }
- #endif
-
- if (Init() == kErr) return -1;
- Process();
- return CleanUp();
- }
-
-
-